home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / man / oldman3 / AVL_Tree.3T < prev    next >
Text File  |  1992-06-26  |  8KB  |  253 lines
  1. .TH AVL_TREE
  2. .SH NAME
  3. AVL_Tree<Type>\f1  A parameterized, height-balanced binary tree class
  4. .SH SYNOPSIS
  5. #include <cool/AVL_Tree.h>
  6. .SH DESCRIPTION
  7. The 
  8.  AVL_Tree< Type > 
  9. class implements height-balanced, dynamic, binary trees. 
  10. The 
  11.  AVL_Tree< Type > 
  12. class is publicly derived from the 
  13.  Binary_Tree< Type > 
  14. class, 
  15. and both are parameterized over some 
  16.  Type . 
  17. An AVL tree is a compromise between 
  18. the expense of a fully balanced binary tree and the desire for efficient search 
  19. times for both average and worst-case scenarios. As a result, an AVL tree maintains a binary tree that is height-balanced, ensuring that the difference 
  20. between the depth of the left subtree and right subtree for every node is no 
  21. more than one.
  22. .PP
  23. The 
  24.  AVL_Tree< Type > 
  25. class implements the notion of a current position. This is 
  26. useful for iterating through the nodes of a tree. The current position is 
  27. maintained in a data member of type 
  28.  AVL_Tree_state 
  29. and is set or reset by all 
  30. member functions affecting elements in the class. Member functions are provided 
  31. to reset the current position, move to the next and previous elements, find an 
  32. element, and get the value at the current position. The \f3Iterator<Type>\f1 class 
  33. provides a mechanism to save and restore the state associated with the current 
  34. position, thus allowing the programmer to use multiple iterators over the same 
  35. instance of a tree.
  36. .PP
  37. The 
  38.  AVL_Tree< Type > 
  39. class inherits all its member functions publicly from the 
  40.  Binary_Tree< Type > 
  41. class. The only member functions that are overloaded are 
  42. those that affect the structure of the tree, thus potentially requiring one or 
  43. more subtrees to be restructured.
  44. .SH Base Classes
  45. \f3Binary_Tree<Type>
  46. .SH Friend Classes
  47. None
  48. .SH Public Constructors
  49. .TP
  50. \f3AVL_Tree<Type> \f3()
  51. Simple constructor to create an empty tree.
  52. .TP
  53. \f3AVL_Tree<Type> (const Binary_Tree<Type>& bt\f3);\f1
  54. Duplicates a 
  55.  Binary_Tree 
  56. object 
  57.  bt , 
  58. adjusting the organization and structure as 
  59. necessary to create an AVL tree.
  60. .TP
  61. \f3AVL_Tree<Type> (const AVL_Tree<Type>& at\f3);\f1
  62. Duplicates the structure of another \f3AVL_Tree<Type>\f1 object 
  63.  at .
  64. .SH Member Functions
  65. .TP
  66.  void balance ();
  67. Builds a perfectly balanced binary tree from the existing tree structure and 
  68. deletes the old tree and storage.
  69. .TP
  70.  void clear ();
  71. Empties the tree and deallocates all memory for nodes and internal structures.
  72. .TP
  73.  inline long count () const;
  74. Returns the number of nodes in the tree structure.
  75. .TP
  76.  inline AVL_Tree_state& current_position ();
  77. Returns a reference to the state information associated with the current 
  78. position. This function should be used with the \f3Iterator<Type>\f1 class to save 
  79. and restore the current position, thus allowing multiple iterators over an 
  80. instance of a binary tree.
  81. .TP
  82. \f3Boolean find (const Type& value\f3);\f1
  83. Searches for 
  84.  value 
  85. in the tree structure. If found, this function updates the 
  86. current position and returns 
  87.  
  88.  TRUE ; 
  89. otherwise, this function invalidates the 
  90. current position and returns 
  91.  
  92.  FALSE .
  93. .TP
  94.  inline Binary_Node* get_root () const;
  95. Accesses the root pointer for the tree structure.
  96. .TP
  97.  Boolean next ();
  98. Advances the current position to the next element in the tree and returns 
  99.  
  100.  TRUE . 
  101. If the current position is invalid, this function sets the current position to 
  102. the first element and returns 
  103.  
  104.  TRUE .  If the current position  is the last 
  105. element of the tree, this function invalidates the current position and returns
  106.  
  107.  FALSE .
  108. .TP
  109. \f3Binary_Node<Type>* \f3node ();\f1
  110. Returns a pointer to the current node object.
  111. .TP
  112. \f3AVL_Tree<Type>& \f3operator= (Binary_Tree<Type>& bt\f3);\f1
  113. Overloads the assignment operator to create an 
  114.  
  115. AVL 
  116. tree from a binary tree 
  117. object
  118.  bt . 
  119. This function returns a reference to the updated AVL tree object.
  120. .TP
  121. \f3AVL_Tree<Type>& \f3operator= (AVL_Tree<Type>& at\f3);\f1
  122. Overloads the assignment operator to duplicate another AVL tree object 
  123.  at.
  124. This 
  125. function returns a reference to the updated AVL tree object.
  126. .TP
  127. \f3inline Boolean operator== (const AVL_Tree<Type>& at\f3) const;\f1
  128. Overloads the equality operator for the \f3AVL_Tree<Type> \f1class. This function 
  129. returns
  130.  
  131.  TRUE
  132. if 
  133.  at 
  134. is equal to the AVL tree object; otherwise, this function 
  135. returns
  136.  
  137.  FALSE .
  138. .TP
  139. \f3inline Boolean operator!= (const AVL_Tree<Type>& at\f3) const;\f1
  140. Overloads the inequality operator for the \f3AVL_Tree<Type>\f1 class. This function 
  141. returns
  142.  
  143.  TRUE 
  144. if
  145.  at 
  146. is unequal to the AVL tree object; otherwise, this function 
  147. returns 
  148.  
  149.  FALSE .
  150. .TP
  151.  Boolean prev ();
  152. Moves the current position to the previous element in the tree and returns 
  153.  
  154.  TRUE .  
  155. If the current position is invalid, this function sets the current 
  156. position to the last element and returns 
  157.  
  158.  TRUE , 
  159. thus facilitating reverse 
  160. traversal through the tree.  If the current position is the first element in 
  161. the object, this function invalidates the current position and returns 
  162.  
  163.  FALSE .
  164. .TP
  165. \f3Boolean put (const Type& value\f3);\f1
  166. Adds the value passed to the tree structure if not already present. This 
  167. function returns 
  168.  
  169.  TRUE
  170. if the item is added; otherwise, this function returns 
  171.  
  172.  FALSE . 
  173. This function invalidates the current position and balances the tree 
  174. structure if necessary.
  175. .TP
  176.  inline Boolean remove ();
  177. Removes the node at the current position from the tree structure and returns
  178.  
  179.  TRUE . 
  180. This function invalidates the current position and balances the tree 
  181. structure if necessary. If the current position is out of range, an 
  182.  \f3\f3Error\f1\f1 
  183. exception is raised and this function returns
  184.  
  185.  FALSE .
  186. .TP
  187. \f3Boolean remove (const Type& value\f3);\f1
  188. Searches for the specified node.  If the node is found, this function removes 
  189. the node and sets the current position to the node immediately follwing the 
  190. node removed; then the function returns 
  191.  
  192.  TRUE .  
  193. If the node is found at the end 
  194. of the tree structure, this function invalidates the current position, balances 
  195. the tree structure if necessary, and returns 
  196.  
  197.  TRUE .  
  198. If the node is not found, 
  199. this function returns 
  200.  
  201.  FALSE . 
  202.  
  203. .TP
  204.  inline void reset ();
  205. Invalidates the current position pointer and deallocates the memory allocated 
  206. for the node cache.
  207. .TP
  208. \f3inline void set_compare (\f2AVL_Tree_Compare \f3= NULL);\f1
  209. Sets the comparison function that is to be used in all comparison tests. 
  210.  AVL_Tree_Compare 
  211. is a function of type 
  212.  Boolean 
  213. (*\f2Function\f1)(\f3const Type&\f1, \f3const Type&\f1). If no argument is provided, the 
  214.  operator== 
  215. for the type over which the 
  216. class is parameterized is used.
  217. .TP
  218.  inline Type& value ();
  219. Returns a reference to the value of the node at the current position. If the 
  220. current position is invalid, an 
  221.  \f3\f3Error\f1\f1 
  222. exception is raised.
  223. .TP
  224.  inline long tree_depth ();
  225. Returns the zero-relative depth of the tree structure. Note that this function 
  226. is potentially very expensive, since the tree depth is calculated by traversing 
  227. all nodes in the tree.
  228. .SH Friend Functions
  229. .TP
  230. \f3friend ostream& operator<< (ostream& \f2os\f3, AVL_Tree<Type>& at\f3);\f1
  231. Accepts an AVL tree reference and outputs the structure by printing it 
  232. sideways, where the root is printed at the left margin. To obtain the standard 
  233. orientation, rotate the output 90 degrees clockwise. This function returns a 
  234. reference to the output stream.
  235. .TP
  236. \f3friend ostream& operator<< (ostream& \f2os\f3, AVL_Tree<Type>* at\f3);\f1
  237. Accepts an AVL tree pointer and outputs the structure by printing it sideways, 
  238. where the root is printed at the left margin. To obtain the standard 
  239. orientation, rotate the output 90 degrees clockwise. This function returns a 
  240. reference to the output stream.
  241. .SH COPYRIGHT
  242.  
  243. Copyright (C) 1991 Texas Instruments Incorporated.
  244.  
  245. Permission is granted to any individual or institution to use, copy, modify,
  246. and distribute this software, provided that this complete copyright and
  247. permission notice is maintained, intact, in all copies and supporting
  248. documentation.
  249.  
  250. Texas Instruments Incorporated provides this software "as is" without
  251. express or implied warranty.
  252.  
  253.